package com.ywk.base.dataStructure.binarytree;
//前缀树（字典树）
public class TriedDemo {

	public static void main(String[] args) {
		Trie t=new Trie();
		t.insert("count");
		t.insert("apple");
		t.insert("app");
		System.out.println(t.search("app"));
	}
}
class Trie {
    private TrieNode root;

    public Trie() {
        root=new TrieNode();
    }
    
    public void insert(String word) {
        TrieNode p=root;
        for(int i=0;i<word.length();i++){
            char curr=word.charAt(i);
            if(!p.isContainsKey(curr)){
                p.put(curr,new TrieNode());
            }
            p=p.gtTrieNode(curr);
        }
        p.isEnd=true;
    }
    
    public boolean search(String word) {
        TrieNode p=root;
        for(int i=0;i<word.length();i++){
            char curr=word.charAt(i);
            if(p.isContainsKey(curr)){
                p=p.gtTrieNode(curr);
            }else{
                return false;
            }
        }
        if(p.isEnd){
            return true;
        }else{
            return false;
        }
    }
    
    public boolean startsWith(String prefix) {
        TrieNode p=root;
        for(int i=0;i<prefix.length();i++){
            char curr=prefix.charAt(i);
            if(p.isContainsKey(curr)){
                p=p.gtTrieNode(curr);
            }else{
                return false;
            }
        }
        return true;
    }
}

class TrieNode{
    public TrieNode[] links;
    public boolean isEnd;

    public TrieNode(){
        links=new TrieNode[26];//每个节点最多能包括26个子节点
    }

    public boolean isContainsKey(char ch){
    	//return links[ch-'a']!=null;
        return links[ch-'a']==null?false:true;//ch-'a'表示26个字母都有对应的索引位置
        //例：a-a等于0，则a在links数组中的索引为0，b为1...以此类推
    }

    public TrieNode gtTrieNode(char ch){
        return links[ch-'a'];
    }

    public void put(char ch,TrieNode node){
        links[ch-'a']=node;
    }
}